/*
 * cPath.java
 *
 * Created on 25. juin 2007, 09:34
 *
 */

package pacman;

import java.util.ArrayList;
import java.util.TreeSet;
import java.util.Collection;
import java.util.Iterator;

/**
 * A path between two points. This class is distance-aware, which means that it tries to find the shortest path between both position.
 * @author jerome
 */
public class cPath {
    TreeSet<node> listeOuverte = new TreeSet<node>();
    TreeSet<node> listeFermee = new TreeSet<node>();
    Object caller;
    cCore parent;
    Position target;
    ArrayList<Position> path = null;
    
    /**
     * Creates a new instance of cPath.
     * @param start The starting point of the path.
     * @param tar The target of the path.
     * @param par The parent core of this path (i.e. the core of the game where the path is created). Needed for accessibility reasons.
     * @param call The caller of the path (i.e. the object who will use the path). Needed for accessibility reasons.
     */   
    
    public cPath(Position start, Position tar, cCore par, Object call) {
        caller = call;
        parent = par;
        this.target = tar;

        node temp = new node(start, this);
        
        //A* starts here...
        listeFermee.add(temp);
        updateOrAdd(listeOuverte, temp.getNeighbours());

        while(!listeOuverte.isEmpty() && !temp.pos.equals(target)) {
            temp = listeOuverte.first();

            listeFermee.add(temp);
            listeOuverte.remove(temp);

            updateOrAdd(listeOuverte, temp.getNeighbours());
        }

        if(temp.pos.equals(tar)) {
            path = new ArrayList<Position>();
            while(!temp.pos.equals(start)) {
                path.add(temp.pos);
                temp = temp.parent;
            }
        }
        //A* ends here
    }
    
    class node implements Comparable{
        int coutH;
        int coutG;
        int coutF;
        Position pos;
        node parent;
        cPath ofPath;

        node(Position p, node par, cPath ofP) {
            pos = p;
            ofPath = ofP;
            parent = par;
            coutG = parent.coutG + 1;
            coutH = distance(p, ofPath.getTarget());
            coutF = coutG + coutH;
        }
        
        node(Position p, cPath ofP) {
            pos = p;
            ofPath = ofP;
            parent = null;
            coutG = 0;
            coutH = distance(p, ofPath.getTarget());
            coutF = coutG + coutH;
        }
        
        private int getCoutF() {
            return coutF;
        }

        public ArrayList<node> getNeighbours() {
            ArrayList<node> temp = new ArrayList<node>();
            Position tmp = pos.clone();
            node tnode;

            //Gets all 4 neighbours and add them to tree
            tmp.incX(1);
            //If the new position is not outside the game, is accessible and is not in listeFermee...
            if(tmp.getX() < ofPath.parent.getPlateau().length && tmp.getX() >= 0 && ofPath.parent.isAccessible(tmp, ofPath.caller)) {
                tnode = new node(tmp.clone(), this, this.ofPath);
                if(findInList(ofPath.listeFermee, tnode) == null) {
                    temp.add(tnode);
                }
            }
            tmp.incX(-2);
            if(tmp.getX() >= 0 && tmp.getX() < ofPath.parent.getPlateau().length && ofPath.parent.isAccessible(tmp, ofPath.caller)) {
               tnode = new node(tmp.clone(), this, this.ofPath);
                if(findInList(ofPath.listeFermee, tnode) == null) {
                    temp.add(tnode);
                }
            }
            tmp.incX(1);
            tmp.incY(1);
            if(tmp.getY() < ofPath.parent.getPlateau()[0].length && tmp.getY() >= 0 && ofPath.parent.isAccessible(tmp, ofPath.caller)) {
               tnode = new node(tmp.clone(), this, this.ofPath);
                if(findInList(ofPath.listeFermee, tnode) == null) {
                    temp.add(tnode);
                }
            }
            tmp.incY(-2);
            if(tmp.getY() >= 0 && tmp.getY() < ofPath.parent.getPlateau()[0].length && ofPath.parent.isAccessible(tmp, ofPath.caller)) {
               tnode = new node(tmp.clone(), this, this.ofPath);
                if(findInList(ofPath.listeFermee, tnode) == null) {
                    temp.add(tnode);
                }
            }
            return temp;
        }

        private int distance(Position p1, Position p2) {
            int dx = p1.getX()-p2.getX();
            int dy = p1.getY()-p2.getY();
            return (dx*dx)+(dy*dy);
        }

        public int compareTo(Object o) {
            if(!(o instanceof node)){
                throw new ClassCastException();
            }
            node n = (node)o;
            if(n.getCoutF() < this.coutF) {
                return 1;
            }
            else if(n.getCoutF() > this.coutF) {
                return -1;
            }
            return 0;
        }
    }
    
    /**
     * Returns the length of the path.
     * @return The length of the path
     */
    public int getLength() {
        if(path != null) {
            return path.size();
        }
        return -1;
    }
    
    /**
     * Returns the next step to be done to parse the path.
     * @return The next position to reach to parse the path.
     */
    public Position getNextStep() {
        if(path != null && path.size() > 0) {
            Position temp = path.get(path.size()-1);
            return temp;
        }
        return new Position(-1, -1);
    }
    
    private Position getTarget() {
        return target;
    }
    
    private node findInList(TreeSet<node> list, node n) {
        Iterator<node> it = list.iterator();
        node k;
        
        while(it.hasNext()) {
            k = it.next();
            if(k.pos.equals(n.pos)) {
                return k;
            }
        }
        return null;
    }
    
    private void updateOrAdd(TreeSet<node> list, ArrayList<node> newNodesArray) {
        for(int i = 0; i < newNodesArray.size(); i++) {
            node k = findInList(list, newNodesArray.get(i));
            if(k != null && k.getCoutF() > newNodesArray.get(i).getCoutF()) {
                list.remove(k);
                list.add(newNodesArray.get(i));
            }
            else if(k == null) {
                list.add(newNodesArray.get(i));
            }
        }
    }
}